package com.tucc.hello.leetcode.no401_800.no752;

import java.util.*;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode
 * @date 2021/5/20
 **/
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] deadends = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        System.out.println(solution.openLock(deadends, target));
    }

    public int openLock(String[] deadends, String target) {
        String start = "0000";
        int count = 0;
        Set<String> deadEndsSet = new HashSet<>();
        for (String deadEnds : deadends) {
            deadEndsSet.add(deadEnds);
        }
        if(deadEndsSet.contains(target) || deadEndsSet.contains(start)){
            return -1;
        }
        if (start.equals(target)) {
            return 0;
        }
        List<String> list = new LinkedList<>();
        list.add(start);
        Set<String> visited = new HashSet<>();
        List<String> nextList = null;
        int[] actions = {-1, 1};
        while (!list.isEmpty()) {
            count++;
            nextList = new LinkedList<>();
            for (String current : list) {
                StringBuilder builder = new StringBuilder(current);
                for (int i = 0; i < target.length(); i++) {
                    for (int j = 0; j < actions.length; j++) {
                        builder.setCharAt(i, move(current, i, actions[j]));
                        String next = builder.toString();
                        if (target.equals(next)) {
                            return count;
                        }
                        if (!visited.contains(next) && !deadEndsSet.contains(next)) {
                            visited.add(next);
                            nextList.add(next);
                        }
                    }
                    builder.setCharAt(i, current.charAt(i));
                }
            }
//            printNext(count, nextList);
            if (nextList.isEmpty()) {
                return -1;
            }
            list = nextList;
        }
        return count;
    }

    private void printNext(int count, List<String> nextList) {
        System.out.println("current rounds " + count + " =========");
        for (String next : nextList) {
            System.out.println(next);
        }
        System.out.println("======================================");
    }

    private char move(String lock, int index, int action) {
        char ch = lock.charAt(index);
        ch += action;
        if (ch > '9') {
            ch = '0';
        } else if (ch < '0') {
            ch = '9';
        }
        return ch;
    }
}
